class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

class Solution {

    /**
     *   解法一
    */
     fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
            if(list1 == null && list2 == null){
                return null
            }else if(list1 == null){
                return list2
            }else if(list2 == null){
                return list1
            }

            var currList1Node:ListNode? = list1
            var currList2Node:ListNode? = list2


            var firstNode:ListNode = if(currList1Node!!.`val` < currList2Node!!.`val`) {
                     val node = currList1Node
                     currList1Node = currList1Node.next
                     node
                    } else {
                     val node = currList2Node
                     currList2Node = currList2Node.next
                     node
                }

            while(true){
                if(currList1Node == null && currList2Node==null){
                    return if(list1.`val` < list2.`val`) list1 else list2  
                }else if(currList1Node==null){
                    firstNode.next = currList2Node
                    return if(list1.`val` < list2.`val`) list1 else list2  
                }else if(currList2Node==null){
                    firstNode.next = currList1Node
                    return if(list1.`val` < list2.`val`) list1 else list2  
                }else{
                    firstNode.next = if(currList1Node.`val` < currList2Node.`val`) {
                     val node = currList1Node
                     currList1Node= currList1Node.next 
                     node
                    } else {
                     val node = currList2Node
                     currList2Node= currList2Node.next 
                     node
                    }

                    firstNode = firstNode.next
                }
            }
    }

    /**
     * 优化解法一（抄自评论）
     */
    fun mergeTwoLists2(list1: ListNode?, list2: ListNode?): ListNode? {
        if(list1 == null){
            return list2
        }else if(list2 == null){
            return list1
        }

        var currList1Node:ListNode? = list1
        var currList2Node:ListNode? = list2

        var firstNode:ListNode = ListNode(0)
        var curr = firstNode;

        while(currList1Node!=null && currList2Node!=null){
            if(currList1Node.`val` < currList2Node.`val`){
                curr.next = currList1Node
                currList1Node = currList1Node.next
            }else{
                curr.next = currList2Node
                currList2Node = currList2Node.next
            }
            curr =curr.next
        }

        curr.next = if(currList1Node==null) currList2Node else currList1Node
        return firstNode.next
    }


    /**
     * 解法三 使用递归
     */

     fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
       if(list1==null) return list2 else if(list2==null) return list1

       if(list1.`val` < list2.`val`){
        list1.next = mergeTwoLists(list1.next, list2)
        return list1
       }else{
        list2.next = mergeTwoLists(list1, list2.next)
        return list2
       }
    }
}